//
//  LinkListSolution.hpp
//  leetcode
//
//  Created by Ellie on 2021/1/31.
//  Copyright © 2021 Ellie. All rights reserved.
//

#ifndef LinkListSolution_hpp
#define LinkListSolution_hpp

#include "DataDefine.h"
#include <queue>
#include <unordered_map>
#include <string>
#include <stack>
#include <vector>
#include <deque>
#include <iostream>
#include <sstream>

using namespace std;

class LinkListSolution
{
public:
    
    // 递归思想
    // Basic Algorithm
    // reverse print
    void reversePrint(ListNode* head, vector<int>& result);
    ListNode* removeElements(ListNode* head, int val);
    // 面试题 02.03. 删除中间节点 脑筋急转弯
    // 237. 删除链表中的节点
    void deleteNode(ListNode* node);
    ListNode* middleNode(ListNode* head);
    
    // 82. 删除排序链表中的重复元素 II 给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
    ListNode* deleteDuplicates(ListNode* head);
    
    // 21. 合并两个有序的链表
    // 合并的过程注意是升序还是降序的问题，合并的是有序的链表
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2);
    ListNode* mergeTwoListsRecursion(ListNode* l1, ListNode* l2);
    // 23. 合并K个升序链表
    ListNode* mergeKLists(vector<ListNode*>& lists);
    ListNode* mergeKListsPriorityQuque(vector<ListNode*>& lists);
    
    // 判断链表是否相交
    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB);
    
    // 面试题 02.02. 返回倒数第 k 个节点
    int kthToLast(ListNode* head, int k);
    // 19. 删除链表的倒数第 N 个结点
    ListNode* removeNthFromEnd(ListNode* head, int n);
    ListNode* removeNthFromEndRecursion(ListNode* head, int n);
    // 2. 两数相加
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2);
    // 445. 两数相加 II
    ListNode* addTwoNumbersReverse(ListNode* l1, ListNode* l2);
    // 61. 旋转链表 // 189. 旋转数组，一样的题目描述，针对链表的处理
    // 将倒数第K个节点作为新的头节点，然后接到原始的头节点上，先成环然后找到K之前的node，断开也可以
    ListNode* rotateRight(ListNode* head, int k);
    
    // 判断链表是否有环+环的起点
    bool hasCycle(ListNode* head);
    ListNode* detectCycle(ListNode* head);
    
    ListNode* insertnode(ListNode* head, int value);
    ListNode* findnode(ListNode* head, int value);
    
    // Algorithm
    
    // 24. 两两交换链表中的节点
    ListNode* swapPairs(ListNode* head);
    ListNode* swapPairsRecursion(ListNode* head);
    
    // 206. 反转链表
    // 画图，两个指针一块走往前走双指针法
    ListNode* reverseList(ListNode* head);
    // 递归翻转整个链表
    ListNode* reverseListRecursion(ListNode* head);
    // 反转前N个节点
    ListNode* recerseNListRecursion(ListNode* head, int N);
    // 92. 反转链表 II
    // 1 ≤ m ≤ n ≤ 链表长度
    ListNode* reverseBetween(ListNode* head, int m, int n);
    ListNode* reverseBetweenRecurion(ListNode* head, int m ,int n);
    
    // 234. 回文链表
    // 需要问下是否能够破坏链表的结构
    bool isPalindromeSimpleVector(ListNode* head);

    ListNode* helperFrontNode;
    bool isPalindrome(ListNode* head);
    
    bool isPalindromRecursion(ListNode* head);
    // 快慢指针方法N的时间复杂度和1的空间复杂度
    bool isPaliandromeSlowFast(ListNode* head);
    
private:
    // 后驱辅助节点
    ListNode* helperSuccessorNode;
    int inthelper = 0;
};

#endif /* LinkListSolution_hpp */
